﻿namespace _5._9._04.SortingAlgorithmsComparison
{
    using System;

    static class SortingAlgorithms
    {
        internal static void SelectionSort<T>(T[] collection) where T : IComparable<T>
        {
            int min;

            for (int i = 0; i < collection.Length - 1; i++)
            {
                min = i;

                for (int j = i + 1; j < collection.Length; j++)
                {
                    if (collection[j].CompareTo(collection[min]) < 0)
                    {
                        min = j;
                    }
                }

                T temp = collection[i];
                collection[i] = collection[min];
                collection[min] = temp;
            }
        }

        internal static void InsertionSort<T>(T[] collection) where T : IComparable<T>
        {
            int j = 0;
 
            for (int i = 1; i < collection.Length; i++ )
            {
                T index = collection[i];
                j = i;
 
                while((j > 0) && (collection[j - 1].CompareTo(index) > 0))
                {
                    collection[j] = collection[j - 1];
                    j = j - 1;
                }
 
                collection[j] = index;
            }
        }

        internal static void Quicksort<T>(T[] collection, int left, int right) where T : IComparable<T>
        {
            int i = left;
            int j = right;

            int pivot = (left / 2 + right / 2);

            while (i <= j)
            {
                while (collection[i].CompareTo(collection[pivot]) < 0)
                {
                    i++;
                }

                while (collection[j].CompareTo(collection[pivot]) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    // Swap
                    T tmp = collection[i];
                    collection[i] = collection[j];
                    collection[j] = tmp;

                    i++;
                    j--;
                }
            }

            // Recursive calls
            if (left < j)
            {
                Quicksort(collection, left, j);
            }

            if (i < right)
            {
                Quicksort(collection, i, right);
            }
        }
    }
}